Graphs are often used to model relationships between entities such as links between websites on the Internet, and between users of social networking applications. With respect to social networks, these graphs may include a node for each user account and a link between nodes that represent social networking relationships between the nodes (e.g., “friends”).
These graphs may be used for a variety of purposes. One use of graphs is to estimate the similarity of nodes in the graph. The similarity of nodes may be used for a variety of purposes including content item recommendation and targeted advertising.
As may be appreciated, such graphs may be extremely large and may include millions or even billions of nodes and edges. As a result, many current techniques for determining the similarity of nodes focus on smaller subsets of the graph. For example, techniques may only consider nodes that are directly connected to a node (or some other degree) when determining the similarity of nodes. However, by limiting the determination to graph subsets, valuable information related to node similarity and node relationships may be lost.